package a08_回溯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * <p>
 * a04_组合总和3
 * </p>
 *
 * @author flyduck
 * @since 2024/12/30
 */
public class a04_组合总和3 {

    //和为n，个数为k
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> resultList = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        traversal(resultList, path, k, n, 0, 1);
        return resultList;
    }

    //1,2,3,4,5,6,7,8,9 k = 5
    //当前已经有path.size个元素了 2
    //需要k - path.size个元素 3
    //最少要从7开始才够 9 - (5-2) + 1
    public void traversal(List<List<Integer>> resultList,
                          LinkedList<Integer> path,
                          int targetCount,
                          int targetSum,
                          int sum,
                          int startIdx){
        if(sum > targetSum){
            return;
        }
        if (path.size() == targetCount ) {
            if(sum == targetSum){
                resultList.add(new ArrayList<>(path));
            }
            return;
        }

        for (int i = startIdx; i <= 9 - (targetCount - path.size()) + 1; i++) {
            path.add(i);
            sum = sum + i;
            traversal(resultList, path, targetCount, targetSum, sum, i + 1);
            sum = sum - i;
            path.removeLast();
        }
    }
}
